package JZ_Offer.algorithm.search;

/**
 * 统计一个数字在排序数组中出现的次数。
 */
public class JZ53_数字在排序数组中出现的次数 {

    /**
     * 二分查找
     */
    static int binarySearch(int[] array, int k) {
        int l = 0, r = array.length;
        while (l < r) {
            int m = (r + l) >> 1;
            int midValue = array[m];
            if (midValue == k) {
                return m;
            } else if (midValue < k) {
                l = m + 1; // l = m  效率差
            } else if (midValue > k) {
                r = m - 1;
            }
        }
        return -1;
    }

    /**
     * 暴力遍历
     */
    public static int GetNumberOfK(int[] array, int k) {
        int count = 0;
        for (int i = 0; i < array.length; i++) {
            if (array[i] == k) {
                count++;
            }
        }
        return count;
    }

    /**
     * 借助二分查找
     */
    public static int GetNumberOfK1(int[] array, int k) {
        int index = binarySearch(array, k);
        if (index < 0) {
            return 0;
        }

        int count = 1;
        // 向左查找
        for (int j = index - 1; j >= 0 && array[j] == k; j--) {
            count++;
        }
        // 向右查找
        for (int j = index + 1; j < array.length && array[j] == k; j++) {
            count++;
        }

        return count;
    }

    public static void main(String[] args) {
        int[] array = {1, 3, 3, 3, 3, 4, 5};
        System.out.println(GetNumberOfK1(array, 3));
    }

}
